package algorithm;

/**
 * @Author pedant
 * @Date 2019/8/29 17:41
 * @Description 求解n皇后问题
 */
public class Queen {
    public static void main(String[] args) {
        getQueen(4);
    }

    public static void getQueen(int n){
        getQueen(0,new int[n]);
    }

    /**
     *
     * @param row 当前行的皇后
     * @param num 已经放好的皇后位置，下标表示行，元素表示第几列
     *            例如：num[0] == 1;表示第一行的皇后在第二列（数组）
     */
    private static void getQueen(int row,int[] num){
        if(row==num.length){//找到一个结果
            for(int i=0;i<num.length;i++){
                System.out.print(num[i]+" ");
            }
            System.out.println();
        }else{
            int i = 0,j = 0;
            for(i=0;i<num.length;i++){
                for(j=0;j<row;j++){
                    if(i==num[j]){//在同一列
                        break;
                    }
                    if(Math.abs(i-num[j])==Math.abs(row-j)){//在同一对角线
                        break;
                    }
                }
                if(j==row){
                    num[row]=i;//第row行的皇后在i列
                    getQueen(row+1,num);
                }
            }
        }
    }
}
